/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann Tübingen, Germany 
 * Niko Schenk Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package collectors.impl;

import util.sedgewick.StdOut;
import util.Interval;
import collectors.api.PreOrderCollector;
import saphre.core.SuffixArray;
import saphre.core.Store;
import util.tokenization_io.BoundarySymbols;
import collectors.impl.visitors.CollectTraversal;
import util.sorting.EquivalenceRelation;
import util.sorting.Multiset;
import util.sedgewick.UnionFind;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;


/**
 * 
 * @author Dale Gerdemann
 */
public class PreOrderLengthenLeftward implements PreOrderCollector {

    Store store;
    SuffixArray sa;
    double D;
    Interval top;
    int n = 0;
    BoundarySymbols tc;
    SuffixArray pa;


    /**
     * 
     * @param store
     * @param sa
     * @param top
     * @param pa 
     */
    public PreOrderLengthenLeftward(Store store, SuffixArray sa, Interval top,
                                    SuffixArray pa) {
        this.store = store;
        this.sa = sa;
        this.top = top;
        tc = store.getTC();
        CollectTraversal.pseudoDepth = 0;
        this.pa = pa;
    }

    /**
     * 
     * @param pa 
     */
    public void addPrefixArray(SuffixArray pa) {
    }

    /*
     * 
     */
    private String spaces(int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2 * n; i++) {
            sb.append(' ');
        }
        return sb.toString();
    }


    /**
     * 
     * @param inter
     * @param parentLcp
     * @param lcp
     * @param depth
     * @return 
     */
    @Override
    public boolean add(Interval inter, int parentLcp, int lcp, int depth) {
        boolean proceed = true;
        EquivalenceRelation eq = new UnionFind(inter.lb(), inter.rb());
        Multiset leftFreq = new Multiset();
        Multiset rightFreq = new Multiset();
        Map<Integer, Integer> left =
                new TreeMap<Integer, Integer>();
        boolean rightPredIncremented = false;
        int predLeftId = -1;
        Map<Integer, Multiset> circumfixes =
                new TreeMap<Integer, Multiset>();
        for (int i = inter.lb(); i <= inter.rb(); i++) {

            // The following two steps use Union-Find. The idea is
            // that some contexts are similar due to sharing of the
            // left context, and some are similar due to sharing of
            // the right context. Occurrences that share in either of
            // these ways should be put together into an equivalence
            // class so that in the end those standalone, non-sharing
            // occurrences can be picked out.

            // Left contexts are unsorted. To spot repetitions, it is
            // necessary to record every left context word (in Map
            // called: left), and make increments (in leftFreq) only
            // when an already seen left context is seen again. Since
            // this undercounts all occurrences by 1, a correction is
            // made later with 'leftFreq.incrAll()'.
            int leftId = store.text[sa.getSuftab()[i] - 1];
            if (!tc.userSentinel(leftId)) {
                if (left.containsKey(leftId)) {
                    eq.unite(i, left.get(leftId)); // Union-Find
                    leftFreq.incr(leftId);
                }
                else {
                    left.put(leftId, i);
                }
            }

            // Right contexts are sorted, making it easier to spot
            // repetitions.
            int rightId = store.text[sa.getSuftab()[i] + lcp];
            if (i != inter.lb() && sa.getLcptab()[i] > lcp) {
                eq.unite(i, i - 1);                  // Union-Find
                if (rightPredIncremented) {
                    rightFreq.incr(rightId);
                    if (!tc.userSentinel(leftId)) {
                        circumfixes.get(rightId).incr(leftId);
                    }
                }
                else {
                    rightFreq.insert(rightId, 2);
                    rightPredIncremented = true;
                    Multiset leftCircum = new Multiset();

                    if (!tc.userSentinel(predLeftId)) {
                        leftCircum.incr(predLeftId);
                    }
                    if (!tc.userSentinel(leftId)) {
                        leftCircum.incr(leftId);
                    }

                    circumfixes.put(rightId, leftCircum);
                }
            }
            else {
                rightPredIncremented = false;
            }
            predLeftId = leftId;
        }
        List<Integer> sing = eq.singletons();
        if (sing.size() > 0) {
            leftFreq.incrAll();
            // rightFreq.incrAll();
            int loc = sa.getSuftab()[inter.lb()];

            // Collect the circumfixes
            StringBuilder circumBuilder = new StringBuilder();
            for (Map.Entry<Integer, Multiset> e : circumfixes.entrySet()) {
                int rightId = e.getKey();
                List<Integer> numberOccur = new ArrayList<Integer>();
                List<Integer> leftIds =
                        e.getValue().freqGreater(1, numberOccur);
                for (int i = 0; i < leftIds.size(); i++) {
                    if (numberOccur.get(i).intValue() > 1) {
                        int leftId = leftIds.get(i);
                        int[] pattern = new int[lcp + 2];
                        pattern[0] = leftId;
                        int cnt = numberOccur.get(i);
                        leftFreq.insert(leftId, -cnt);
                        rightFreq.insert(rightId, -cnt);
                    }
                }
            }


            String pref = "pref:" + leftFreq.toStringWF(store) + " ";
            if (pref.length() == 8) {
                pref = "";
            }


            StringBuilder suffBuilder = new StringBuilder();
            int[] seed = store.toArray(loc, loc + lcp);
            int[] pattern = new int[seed.length + 1];
            for (int j = 0; j < seed.length; j++) {
                pattern[j] = seed[j];
            }
            for (Multiset.Elem e : rightFreq.asList()) {
                if (e.getValue() == 0) {
                    continue;
                }
                pattern[seed.length] = e.getKey();
                int[] max = sa.maximize(pattern, top, sa, pa, store);
                suffBuilder.append("   " + store.toString(max));
                suffBuilder.append("\n");
            }
            String suff = suffBuilder.toString();
            if (suffBuilder.length() > 0) {
                StdOut.print(spaces(2 * depth)
                        + store.toString(loc, loc + lcp) + " "
                        + "==> \n"
                        + suff
                );
                System.out.println("\n");
            }
        }
        if (sing.size() > 0) {
            return true;
        }
        else {
            return true;
        }
    }

    /**
     * 
     * @param inter
     * @param lcp
     * @param depth 
     */
    @Override
    public void addTrivial(Interval inter, int lcp, int depth) {

    }
}
